#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""
class Solution:
    def subsetsWithDup(self, nums):
        self.ret = []
        self.ret.append([])
        self.nums = nums
        self.nums.sort()
        self.len = len(nums)

        # self.loop()
        self.rec_sub(0, [])
        return self.ret

    def rec_sub(self, begin, sub_path):
        # processed_set = set()       # 在q17基础上添加set

        for i in range(begin, self.len):
            v = self.nums[i]
            # if v in processed_set:
            #     continue
            # processed_set.add(v)

            # 因为self.nums已经排序过, 所以只用判断是否不是begin, 并且不和前一个相同:
            # 如果没有排序过: 使用set判断
            # 就可以知道有没有在这个栈的循环中处理过
            # 使用set() 判断processed比较直观: 但浪费和空间和判断时间
            if i != begin and v == self.nums[i-1]:
                continue

            new_sub_path = sub_path + [v]
            self.ret.append(new_sub_path)
            self.rec_sub(i+1, new_sub_path)


def main():
    print("start main")
    s = Solution()
    ret = s.subsetsWithDup([1,2,2])
    print(ret)

if __name__ == "__main__":
    main()
